package SlideWindows;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class L239_SlidingWinSum {
    static class AscQueue{
        static Deque<Integer> data = new LinkedList<>();
        //把所有小于n的都提出去，保持单调递增，小于n的都已经不需要了
        static void push(int n){
            while ( !data.isEmpty() && data.getLast() < n)
                data.pollLast();//队尾去除
            data.addLast(n);//从队尾加入
        }
        static int max(){
            return data.getFirst();
        }//获取当前最大
        //先push，再pop的，所以，小于n的都已经被pop出去了
        static void pop(int n){
            if( !data.isEmpty() && data.getFirst() == n){
                data.pollFirst();//最大的队首出队列
            }
        }
    }

    /**
     * 1.题意理解错了，我还以为是求总和，原来是求最大的数
     * 这题没那么简单，不是直接的 max = Math.max(max,xx);  可以用双端队列(弄个单调递增的) 或者 弄个最大堆
     https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k==0) return new int[0];
        int n = nums.length;
        int[] res = new int[n - k +1];

        int left=0, right=0, i=0;
        while (right < n){
            if( (right-left + 1) < k){
                AscQueue.push(nums[right]);
            }else{
                AscQueue.push(nums[right]);
                res[i] = AscQueue.max();
                AscQueue.pop(nums[left]);
                //这几个自增记得加
                left++;i++;
            }
            //外面这个也记得加
            right++;
        }
        return res;
    }

    public static void main(String[] args){
        L239_SlidingWinSum l = new L239_SlidingWinSum();
        int[] n = new int[]{1};
        l.maxSlidingWindow(n, 1);
    }
}
